// uses Range Minimum Query functions
// A - Connections list
// B - Way; CC - length of WAY

type
  ar=array of longint;

var
  used,was:array[0..100010] of boolean;
  k,cc:longint;
  a:array[0..100010] of ar;
  b:array[0..500010] of longint;
  first:array[0..100010] of longint;
  
procedure mark(v:longint);
begin
inc(cc);
b[cc]:=v;
if not used[v] then begin
	used[v]:=true;
	first[v]:=cc;
end;
end;

procedure dfs(v:longint);
var
	i,k:longint;
begin
mark(v);	
was[v]:=true;
k:=length(a[v])-1;
for i:=0 to k do 
	if (not was[a[v][i]]) then begin
		dfs(a[v][i]);
		mark(v);
	end;
end;

procedure precalc;
begin
fillchar(was,sizeof(was),0);
fillchar(used,sizeof(used),0);
dfs(1);
k:=build(cc);
end;

function lca(l,r:longint):longint; // returns index
begin
if l>r then swap(l,r);
result:=rmq(l,r);
end;
